package com.nanbei.sort;

import java.util.Arrays;

/**
 * @ClassDescription: 快速排序 (双边快排)
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/6/26 17:02
 */
public class QuickSortHoare {

    public static void main(String[] args) {
        int[] ints = {6, 1, 3, 2, 4, 5, 9, 7, 8};
        int[] bubbling = QuickSortHoare.selection(ints);
        System.out.println(Arrays.toString(bubbling));
    }


    public static int[] selection(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = querySort(nums, left, right);
        sort(nums, left, i - 1);
        sort(nums, i + 1, right);
    }

    /**
     * - 选择最左侧元素作为基准点
     * 选择基准点：通常选择数组的第一个元素（最左侧元素）作为基准点。
     * 从右到左查找：从数组的右侧开始查找，直到找到一个小于基准点的元素。
     * 从左到右查找：从数组的左侧开始查找，直到找到一个大于基准点的元素。
     * 交换：交换上一步找到的两个元素。
     * 重复上述步骤：直到左右指针交错。
     *
     * nums[left] 为基准点时需要先 从右向左找小的、在从左向右找大的
     * nums[right] 为基准点时需要先 从左向右找大的、从右向左找小的
     *
     * @param nums  数组
     * @param left  左边界
     * @param right 右边界
     * @return 基点下标
     */
    private static int querySort(int[] nums, int left, int right) {
        int max = right, min = left;
        int pv = nums[left];
        while (min < max) {
            // 从右向左找小的
            while (min < max && nums[max] > pv) {
                max--;
            }
            // 从左向右找大的
            while (min < max && nums[min] <= pv) {
                min++;
            }
            // 找到后交换位置
            swap(nums, max, min);
        }

        swap(nums, left, min);
        return min;

    }

    public static void swap(int[] nums, int i, int j) {
        Sort.swap(nums, i, j);
    }


}
